/**
 * @param {number} n
 * @return {number}
 */
export var nextGreaterElement = function (n) {
  const nums = n.toString().split('').map(Number)
  const pn = permute(nums)
  let ans = -1
  for (let i = 0; i < pn.length; i++) {
    const pnNum = pn[i].join('')
    // console.log(pnNum)
    if (BigInt(pnNum) > BigInt(2 ** 32)) continue
    if (pnNum > n && (ans === -1 || ans > pnNum)) ans = pnNum
  }
  return parseInt(ans)
}

/**
 * 全排列
 * @param {number[]} nums
 * @returns
 */
var permute = function (nums) {
  const ans = []
  dfs(nums, [], [], ans)
  return ans
}

function dfs(nums, path, indexPath, ans) {
  if (path.length === nums.length) {
    ans.push(path.slice())
    return
  }
  for (let i = 0; i < nums.length; i++) {
    const cur = nums[i]
    // console.log('cur', cur, 'ans', ans, 'path', path)
    if (indexPath.includes(i)) continue
    path.push(cur)
    indexPath.push(i)
    dfs(nums, path, indexPath, ans)
    path.pop()
    indexPath.pop()
  }
}

/**
 * @param {number} n
 * @return {number}
 */
export var nextGreaterElement2 = function (n) {
  // 把 n 字符串化
  const nStr = n + ''
  const len = nStr.length
  // 我们从后往前遍历，找到第一个比他后面的最大数字小的一个数字，这个位置的数字就是我们要更换的数字
  let max = nStr[len - 1]

  // 已经遍历过的数字组成的数字，当我们已经更换的数字更换了之后，这个数组就保存更换数字之后的所有数字，我们取得这个数组能组成的数字的最小值拼接在后面即可
  const after = [max]

  // 需要更换的数字的位置
  let before = -1
  for (let i = len - 2; i >= 0; i--) {
    if (nStr[i] < max) {
      before = i
      break
    } else {
      max = nStr[i]
      after.unshift(nStr[i])
    }
  }

  // 当没有需要更换的数字，表示重排找不到比 n 最大的数字了，返回 -1
  if (before < 0) return -1

  // 保存需要更换的数字
  let num = nStr[before]

  // after数组从小到大排序，到时候直接拼接就是能组合的最小数字
  after.sort((a, b) => a - b)

  // 遍历after数组，找到第一个比 num 大的数，来和 num 做交换
  for (let i = 0, len = after.length; i < len; i++) {
    if (after[i] > num) {
      const temp = after[i]
      after[i] = num
      num = temp
      break
    }
  }

  // 拼接数字
  // 需要更换的数字之前 + 更换的后数字 + 更换的数字位置之后的所有数字能组成的最小数字
  const ret = +(nStr.slice(0, before) + num + after.join(''))

  return ret <= 2 ** 31 - 1 ? ret : -1
}

/**
  1 5 8 4 7 6 5 3 1
  从右向左找到第一个比后一数小的数 a
  1 5 8 4 7 6 5 3 1
        。
  然后从最右向左找到第一个比 a 大的数 b
  1 5 8 4 7 6 5 3 1
        。    。
  交换这两个数 [num[a], num[b]] = [num[b], num[a]]
  1 5 8 5 7 6 4 3 1  
        。    。
  将 a 右边的数全部反转
  1 5 8 5 1 3 4 6 7
        。    
  done!
*/

/**
 * 与方法2一样
 * @param {number} n
 * @return {number}
 */
export var nextGreaterElement3 = function (n) {
  // 把 n 字符串化
  const s = String(n)
  const len = s.length
  let max = s[len - 1]

  let [a, b] = [-1, -1]
  // 从右向左找到第一个比后一数小的数 a
  for (let i = len - 2; i >= 0; i--) {
    if (s[i] < max) {
      a = i
      break
    }
    max = s[i]
  }

  if (a < 0) return -1

  // 从最右向左找到第一个比 a 大的数 b
  for (let i = len - 1; i >= a; i--) {
    if (s[i] > s[a]) {
      b = i
      break
    }
  }

  // 交换这两个数 [num[a], num[b]] = [num[b], num[a]]
  let sArr = s.split('')
  ;[sArr[a], sArr[b]] = [sArr[b], sArr[a]]
  //把a后边的数按小到大排序
  const ans =
    sArr.slice(0, a + 1).join('') +
    sArr
      .slice(a + 1)
      .reverse()
      .join('')
  return +ans <= 2 ** 31 - 1 ? +ans : -1
}
